////////////////////////////////////////////////////////////////////////////////
// Copyright (C) 2008 Michiel Helvensteijn                                    //
//                                                                            //
// This file is part of the Mist compiler.                                    //
//                                                                            //
// The Mist compiler is free software: you can redistribute it and/or modify  //
// it under the terms of the GNU General Public License as published by       //
// the Free Software Foundation, either version 3 of the License, or          //
// (at your option) any later version.                                        //
//                                                                            //
// The Mist compiler is distributed in the hope that it will be useful,       //
// but WITHOUT ANY WARRANTY; without even the implied warranty of             //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              //
// GNU General Public License for more details.                               //
//                                                                            //
// You should have received a copy of the GNU General Public License          //
// along with the Mist compiler.  If not, see <http://www.gnu.org/licenses/>. //
////////////////////////////////////////////////////////////////////////////////

/******************************************************************************
 * Initial Code                                                               *
 ******************************************************************************/

%code requires {
	#include <string>
	using std::string;
	
	#include <vector>
	using std::vector;
	
	#include <typeinfo>
	
	#include <boost/foreach.hpp>
	#define foreach BOOST_FOREACH
	
	#include <boost/shared_ptr.hpp>
	using boost::shared_ptr;
	using boost::dynamic_pointer_cast;

	#include "bigint.hpp"
	#include "ast/nodetypes.hpp"
	#include "messages.hpp"
	#include "parameterpolicy.hpp"
	
	typedef void* yyscan_t;
	
	struct FormalParameter {
		FormalParameter(shared_ptr<ParameterPolicy> p, shared_ptr<Type> t, shared_ptr<Identifier> n) : policy(p), type(t), name(n) {}
		
		shared_ptr<ParameterPolicy> policy;
		shared_ptr<Type>            type;
		shared_ptr<Identifier>      name;
	};
}

/******************************************************************************
 * Options                                                                    *
 ******************************************************************************/

/* Generate a C++ LALR(1) parser class */
%skeleton "lalr1.cc"

/* Require Bison version 2.3 */
%require "2.3"

/* Generate bisonparser.tab.hpp, for use by flex */
%defines

/* Parse function parameters */
%parse-param { shared_ptr<Node>& output }
%parse-param { yyscan_t yyscanner }
%parse-param { shared_ptr<Messages> messages }
%parse-param { string filename }

/* Flex parameters */
%lex-param { yyscanner }

/* Enable location tracking */
%locations

/* Name the class BisonParser (not Parser, which supervises this one) */
%define "parser_class_name" "BisonParser"

/* Name the output files bisonparser.tab.cpp and bisonparser.tab.hpp */
%output="bisonparser.tab.cpp"

/* Enable parser debugging
%debug
//*/

/* Produce verbose error messages to yyerror */
%error-verbose

/* Start symbol */
%start start

%initial-action {
	// Initialize the initial location.
	@$.begin.filename = @$.end.filename = &filename;
	@$.begin.line     = @$.end.line     = 1;
	@$.begin.column   = @$.end.column   = 0;
};

/******************************************************************************
 * Terminal and Non-terminal symbols                                          *
 ******************************************************************************/

%union {
	BigInt*                          number;
	bool                             boolean;
	string*                          str;
	vector<ParameterType>*           parametertypelist;
	vector<FormalParameter>*         formalparameterlist;
	vector<shared_ptr<Expression> >* expressionlist;
	vector<shared_ptr<Assertion> >*  assertionlist;
	shared_ptr<ParameterPolicy>*     parameterpolicy;
	FormalParameter*                 formalparameter;
	
	shared_ptr<Node>*                node;
	shared_ptr<Assertion>*           assertion;
	shared_ptr<Assignment>*          assignment;
	shared_ptr<IdAssignment>*        idassignment;
	shared_ptr<BooleanLiteral>*      booleanliteral;
	shared_ptr<Null>*                nullptr;
	shared_ptr<CompoundStatement>*   compoundstatement;
	shared_ptr<Expression>*          expression;
	shared_ptr<FunctionCall>*        functioncall;
	shared_ptr<FunctionType>*        functiontype;
	shared_ptr<IfStatement>*         ifstatement;
	shared_ptr<IntegerLiteral>*      integerliteral;
	shared_ptr<Statement>*           statement;
	shared_ptr<Type>*                type;
	shared_ptr<UnaryOperation>*      unaryoperation;
	shared_ptr<Identifier>*          identifier;
	shared_ptr<WhileStatement>*      whilestatement;
	shared_ptr<FunctionDeclaration>* functiondeclaration;
	shared_ptr<VariableDeclaration>* variabledeclaration;
	shared_ptr<Declarations>*        declarations;
	shared_ptr<Subscripting>*        subscripting;
	shared_ptr<Declaration>*         declaration;
	shared_ptr<ForStatement>*        forstatement;
	shared_ptr<Range>*               range;
	shared_ptr<Reference>*           reference;
};

/******************************************************************************
 * Giving string-literals to some terminal symbols                            *
 ******************************************************************************/

%token VAL_ASSIGN_OP        "<-"
%token ID_ASSIGN_OP         "<--"
%token OR_OP                "or"
%token AND_OP               "and"
%token IMPLIES_OP           "=>"
%token LE_OP                "<="
%token GE_OP                ">="
%token LG_OP                "<>"
%token LGE_OP               "<>="
%token NE_OP                "!="
%token NL_OP                "!<"
%token NG_OP                "!>"
%token NLE_OP               "!<="
%token NGE_OP               "!>="
%token NLG_OP               "!<>"
%token NLGE_OP              "!<>="
%token ID_OP                "=="
%token NOT_ID_OP            "!=="
%token MOD_OP               "mod"
%token VAL                  "val"
%token REF                  "ref"
%token ALS                  "als"
%token PRE                  "pre"
%token POST                 "post"
%token BODY                 "body"
%token INT                  "int"
%token BOOL                 "bool"
%token VOID                 "void"
%token IF                   "if"
%token ELSE                 "else"
%token WHILE                "while"
%token FOR                  "for"
%token RANGE_OP             ".."
%token FUNCTION             "function"
%token NULLPTR              "null"
%token END                0 "end of file"

/******************************************************************************
 * Entry points                                                               *
 ******************************************************************************/

%token ENTER_DECLARATIONS
%token ENTER_FUNCTIONTYPE
%token ENTER_STATEMENT
%token ENTER_EXPRESSION

/******************************************************************************
 * Rule Types                                                                 *
 ******************************************************************************/

%type <declarations>          declarations
%type <functiondeclaration>   functiondeclaration
%type <variabledeclaration>   variabledeclaration
%type <formalparameterlist>   formalparameterlist
%type <formalparameter>       formalparameter
%type <parameterpolicy>       parameterpolicy
%type <assertionlist>         functionprecondition
%type <assertionlist>         functionpostcondition
%type <functiontype>          functiontype
%type <parametertypelist>     parametertypelist
%type <type>                  type
%type <type>                  strongtype
%type <compoundstatement>     compoundstatement
%type <compoundstatement>     statementblock
%type <assertionlist>         assertions
%type <assertion>             assertion
%type <statement>             statement
%type <expression>            expression
%type <subscripting>          subscripting
%type <assignment>            assignment
%type <idassignment>          idassignment
%type <functioncall>          functioncall
%type <expressionlist>        expressionlist
%type <ifstatement>           ifstatement
%type <whilestatement>        whilestatement
%type <integerliteral>        integerliteral
%type <booleanliteral>        booleanliteral
%type <nullptr>               nullptr
%type <identifier>            identifier
%type <variabledeclaration>   variabledeclarations
%type <expression>            valueinit
%type <expression>            identityinit
%type <forstatement>          forstatement
%type <range>                 range
%type <reference>             reference

/******************************************************************************
 * Various Token Declarations                                                 *
 ******************************************************************************/

%token <str>     IDENTIFIER
%token <number>  NUMBER
%token <boolean> BOOL_LITERAL
%token           ASSERTION_END

/******************************************************************************
 * Precedence Rules                                                           *
 ******************************************************************************/

/* Precedence rule to resolve dangling else conflict */
%nonassoc ')'
%nonassoc "else"

/* Precedence and associativity rules to resolve operator conflicts */
%right "<-" "<--"
%left  "=>"
%left  "or"
%left  "and"
%left  '=' '<' '>' "<=" ">=" "<>" "<>=" "!=" "!<" "!>" "!<=" "!>=" "!<>" "!<>=" "==" "!=="
%left  '+' '-'
%left  '*' '/' "mod"
%nonassoc '!' '#' UMINUS
%nonassoc '(' '['

/******************************************************************************
 * Some Code                                                                  *
 ******************************************************************************/

%{
	#include "lexer.lex.hpp"
	
	#include <iostream>
	using std::cerr;
	
	shared_ptr<FunctionDeclaration>* create_function_declaration(shared_ptr<Type> returnType,
	                                                             shared_ptr<Identifier> name,
	                                                             const vector<FormalParameter>& params,
	                                                             shared_ptr<CompoundStatement> statement,
	                                                             const vector<shared_ptr<Assertion> >& precondition,
	                                                             const vector<shared_ptr<Assertion> >& postcondition,
	                                                             CodeLocation location) {
		shared_ptr<FunctionDeclaration>* result = new shared_ptr<FunctionDeclaration>(FunctionDeclaration::create());
		(*result)->set_name(name);
		(*result)->set_type(FunctionType::create());
		(*result)->type()->set_return_type(returnType);
		(*result)->set_statement(statement);
		(*result)->set_location(location);
		
		foreach (shared_ptr<Assertion> assertion, precondition)
			(*result)->insert_precondition(assertion);
		
		foreach (shared_ptr<Assertion> assertion, postcondition)
			(*result)->insert_postcondition(assertion);
		
		foreach (FormalParameter param, params) {
			(*result)->type()->insert_parameter_type(ParameterType(param.policy, param.type));
			(*result)->insert_parameter_name(param.name);
		}
		
		return result;
	}
	
	void yy::BisonParser::error(yy::location const& loc, string const& message) {
		if (messages)
			messages->add(Error, loc, message);
	}
%}

%%

/******************************************************************************
 * Grammar Rules                                                              *
 ******************************************************************************/

start: ENTER_DECLARATIONS declarations {
       	output = *$2;
       	output->set_location(@2);
       	delete $2;
       }
     | ENTER_FUNCTIONTYPE functiontype {
       	output = *$2;
       	output->set_location(@2);
       	delete $2;
       }
     | ENTER_STATEMENT statement {
       	output = *$2;
       	output->set_location(@2);
       	delete $2;
       }
     | ENTER_EXPRESSION expression {
       	output = *$2;
       	output->set_location(@2);
       	delete $2;
       }
     ;

declarations: declarations functiondeclaration {
              	$$ = $1;
              	(*$$)->insert_declaration(*$2);
              	(*$$)->set_location(@$);
              	delete $2;
              }
            | declarations variabledeclaration ';' {
              	$$ = $1;
              	(*$$)->insert_declaration(*$2);
              	(*$$)->set_location(@$);
              	delete $2;
              }
            | declarations error {
              	$$ = $1;
              	(*$$)->set_location(@$);
              }
            | /*empty*/ {
              	$$ = new shared_ptr<Declarations>(Declarations::create());
              }
            ;

functiondeclaration: /*--- No pre/post-conditions ---*/
                     type identifier '(' formalparameterlist ')' '{' statementblock '}' {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$7, vector<shared_ptr<Assertion> >(), vector<shared_ptr<Assertion> >(), @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $7;
                     }
                   | type identifier '(' formalparameterlist ')' "body" '{' statementblock '}' {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$8, vector<shared_ptr<Assertion> >(), vector<shared_ptr<Assertion> >(), @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $8;
                     }
                     /*--- Only precondition ---*/
                   | type identifier '(' formalparameterlist ')' '{' statementblock '}' functionprecondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$7, *$9, vector<shared_ptr<Assertion> >(), @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $7;
                     	delete $9;
                     }
                   | type identifier '(' formalparameterlist ')' "body" '{' statementblock '}' functionprecondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$8, *$10, vector<shared_ptr<Assertion> >(), @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $8;
                     	delete $10;
                     }
                   | type identifier '(' formalparameterlist ')' functionprecondition "body" '{' statementblock '}' {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$9, *$6, vector<shared_ptr<Assertion> >(), @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $6;
                     	delete $9;
                     }
                     /*--- Only postcondition ---*/
                   | type identifier '(' formalparameterlist ')' '{' statementblock '}' functionpostcondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$7, vector<shared_ptr<Assertion> >(), *$9, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $7;
                     	delete $9;
                     }
                   | type identifier '(' formalparameterlist ')' "body" '{' statementblock '}' functionpostcondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$8, vector<shared_ptr<Assertion> >(), *$10, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $8;
                     	delete $10;
                     }
                   | type identifier '(' formalparameterlist ')' functionpostcondition "body" '{' statementblock '}' {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$9, vector<shared_ptr<Assertion> >(), *$6, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $6;
                     	delete $9;
                     }
                     /*--- Pre- and postcondition ---*/
                   | type identifier '(' formalparameterlist ')' '{' statementblock '}' functionprecondition functionpostcondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$7, *$9, *$10, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $7;
                     	delete $9;
                     	delete $10;
                     }
                   | type identifier '(' formalparameterlist ')' "body" '{' statementblock '}' functionprecondition functionpostcondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$8, *$10, *$11, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $8;
                     	delete $10;
                     	delete $11;
                     }
                   | type identifier '(' formalparameterlist ')' functionprecondition "body" '{' statementblock '}' functionpostcondition {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$9, *$6, *$11, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $6;
                     	delete $9;
                     	delete $11;
                     }
                   | type identifier '(' formalparameterlist ')' functionprecondition functionpostcondition "body" '{' statementblock '}' {
                     	$$ = create_function_declaration(*$1, *$2, *$4, *$10, *$6, *$7, @$);
                     	delete $1;
                     	delete $2;
                     	delete $4;
                     	delete $6;
                     	delete $7;
                     	delete $10;
                     }
                   ;

functionprecondition: "pre" '{' assertions '}' {
                      	$$ = $3;
                      }
                    ;

functionpostcondition: "post" '{' assertions '}' {
                       		$$ = $3;
                       }
                     ;

variabledeclaration: type variabledeclarations {
                     	$$ = $2;
                     	(*$$)->set_type(*$1);
                     	(*$$)->set_location(@$);
                     	delete $1;
                     }
                   ;

variabledeclarations: variabledeclarations ',' identifier {
                      	$$ = $1;
                      	(*$$)->insert_variable(VarDec(*$3));
                      	delete $3;
                      }
                    | variabledeclarations ',' identifier valueinit {
                      	$$ = $1;
                      	(*$$)->insert_variable(VarDec(*$3, *$4, false));
                      	delete $3;
                      	delete $4;
                      }
                    | variabledeclarations ',' identifier identityinit {
                      	$$ = $1;
                      	(*$$)->insert_variable(VarDec(*$3, *$4, true));
                      	delete $3;
                      	delete $4;
                      }
                    | identifier valueinit {
                      	$$ = new shared_ptr<VariableDeclaration>(VariableDeclaration::create());
                      	(*$$)->insert_variable(VarDec(*$1, *$2, false));
                      	delete $1;
                      	delete $2;
                      }
                    | identifier identityinit {
                      	$$ = new shared_ptr<VariableDeclaration>(VariableDeclaration::create());
                      	(*$$)->insert_variable(VarDec(*$1, *$2, true));
                      	delete $1;
                      	delete $2;
                      }
                    | identifier {
                      	$$ = new shared_ptr<VariableDeclaration>(VariableDeclaration::create());
                      	(*$$)->insert_variable(VarDec(*$1));
                      	delete $1;
                      }
                    ;

valueinit: "<-" expression {
              	$$ = $2;
              }
            ;

identityinit: "<--" expression {
              	$$ = $2;
              }
            ;

formalparameterlist: formalparameterlist ',' formalparameter {
                     	$$ = $1;
                     	$$->push_back(*$3);
                     	delete $3;
                     }
                   | formalparameter {
                     	$$ = new vector<FormalParameter>;
                     	$$->push_back(*$1);
                     	delete $1;
                     }
                   | /* empty */ {
                     	$$ = new vector<FormalParameter>;
                     }
                   ;

formalparameter: parameterpolicy type identifier {
                 	$$ = new FormalParameter(*$1, *$2, *$3);
                 	delete $1;
                 	delete $2;
                 	delete $3;
                 }
               ;

parameterpolicy: "val"       { $$ = new shared_ptr<ParameterPolicy>(ParameterPolicy::ByValue);               }
               | "ref"       { $$ = new shared_ptr<ParameterPolicy>(ParameterPolicy::ByReference);           }
               | "als"       { $$ = new shared_ptr<ParameterPolicy>(ParameterPolicy::ByAlias);               }
               | /* empty */ { $$ = new shared_ptr<ParameterPolicy>(ParameterPolicy::ByValue); /* default */ }
               ;

type: strongtype
    | strongtype '^' {
      	$$ = $1;
      	(*$$)->set_weak_pointer(true);
      	(*$$)->set_location(@$);
      }
    ;

strongtype: "int" {
            	$$ = new shared_ptr<Type>(IntegerType::create());
            	(*$$)->set_location(@$);
            }
          | "bool" {
            	$$ = new shared_ptr<Type>(BooleanType::create());
            	(*$$)->set_location(@$);
            }
          | type '[' integerliteral ']' {
            	$$ = new shared_ptr<Type>(ArrayType::create(*$3, *$1));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          | "void" {
            	$$ = new shared_ptr<Type>(VoidType::create());
            	(*$$)->set_location(@$);
            }
          ;

functiontype: '(' type ')' "function" '(' parametertypelist ')' {
              	$$ = new shared_ptr<FunctionType>(FunctionType::create());
              	(*$$)->set_return_type(*$2);
              	foreach (ParameterType t, *$6)
              		(*$$)->insert_parameter_type(t);
              	(*$$)->set_location(@$);
              	delete $2;
              	delete $6;
              }
            ;

parametertypelist: parametertypelist ',' parameterpolicy type {
                   	$$ = $1;
                   	$$->push_back(ParameterType(*$3, *$4));
                   	delete $3;
                   	delete $4;
                   }
                 | parameterpolicy type {
                   	$$ = new vector<ParameterType>;
                   	$$->push_back(ParameterType(*$1, *$2));
                   	delete $1;
                   	delete $2;
                   }
                 | /* empty */ {
                   	$$ = new vector<ParameterType>;
                   }
                 ;

compoundstatement: '{' statementblock '}' {
                   		$$ = $2;
                   		(*$$)->set_location(@$);
                   }
                 | identifier '{' statementblock '}' {
                   		$$ = $3;
                   		(*$$)->set_name(*$1);
                   		(*$$)->set_location(@$);
                   		delete $1;
                   }
                 ;

statementblock: statementblock statement {
                	$$ = $1;
                	(*$$)->insert_statement(*$2);
                	delete $2;
                }
              | statementblock assertiondummy {
                	$$ = $1;
                }
              | statementblock error {
                	$$ = $1;
                }
              | /* empty */ {
                	$$ = new shared_ptr<CompoundStatement>(CompoundStatement::create());
                }
              ;

assertions: assertions assertion {
            	$$->push_back(*$2);
            	delete $2;
            }
          | assertions assertiondummy {
            	$$ = $1;
            }
          | assertions error {
            	$$ = $1;
            }
          | /* empty */ {
            	$$ = new vector<shared_ptr<Assertion> >;
            }
          ;

assertion: '@' expression ASSERTION_END {
           		$$ = new shared_ptr<Assertion>(Assertion::create(*$2));
           		(*$$)->set_location(CodeLocation(CodeLocation(@1).begin(), CodeLocation(@2).end()));
           		delete $2;
           }
         |
           '@' variabledeclaration ASSERTION_END {
           		$$ = new shared_ptr<Assertion>(Assertion::create(*$2));
           		(*$$)->set_location(CodeLocation(CodeLocation(@1).begin(), CodeLocation(@2).end()));
           		delete $2;
           }
         ;

assertiondummy: '@' ASSERTION_END /* Sometimes nice for readability to use an empty assertion. */
              ;

statement: variabledeclaration ';' { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | assignment          ';' { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | idassignment        ';' { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | functioncall        ';' { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | functiondeclaration     { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | ifstatement             { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | whilestatement          { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | forstatement            { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | assertion               { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         | compoundstatement       { $$ = new shared_ptr<Statement>(*$1); delete $1; }
         ;

expression: integerliteral     { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | booleanliteral     { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | nullptr            { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | functioncall       { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | reference          { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | subscripting       { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | assignment         { $$ = new shared_ptr<Expression>(*$1); delete $1; }
          | idassignment       { $$ = new shared_ptr<Expression>(*$1); delete $1; }

            /************** Pointer literals **************/

          | "int" '(' expression ')' {
            	$$ = new shared_ptr<Expression>(IntegerPointerLiteral::create(*$3));
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | "bool" '(' expression ')' {
            	$$ = new shared_ptr<Expression>(BooleanPointerLiteral::create(*$3));
            	(*$$)->set_location(@$);
            	delete $3;
          }

            /************** Unary operations **************/

          | '!' expression {
            	$$ = new shared_ptr<Expression>(UnaryOperation::create(NotOperator, *$2));
            	(*$$)->set_location(@$);
            	delete $2;
            }
          | '-' expression %prec UMINUS {
            	$$ = new shared_ptr<Expression>(UnaryOperation::create(UnaryMinusOperator, *$2));
            	(*$$)->set_location(@$);
            	delete $2;
            }
          | '#' expression {
            	$$ = new shared_ptr<Expression>(UnaryOperation::create(CountOperator, *$2));
            	(*$$)->set_location(@$);
            	delete $2;
            }

            /************** Binary operations *************/

          | expression '+' expression {
            	$$ = new shared_ptr<Expression>(ArithmeticOperation::create(*$1, BinaryPlusOperator, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          | expression '-' expression {
            	$$ = new shared_ptr<Expression>(ArithmeticOperation::create(*$1, BinaryMinusOperator, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          | expression '*' expression {
            	$$ = new shared_ptr<Expression>(ArithmeticOperation::create(*$1, MultiplicationOperator, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          | expression '/' expression {
            	$$ = new shared_ptr<Expression>(ArithmeticOperation::create(*$1, DivisionOperator, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          | expression "mod" expression {
            	$$ = new shared_ptr<Expression>(ArithmeticOperation::create(*$1, ModuloOperator, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }

            /*************** Logic-chain expressions ********************/

          | expression "=>" expression {
            	if (typeid(**$1) == typeid(ImpliesChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ImpliesChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ImpliesChain::create(*$1, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "and" expression {
            	if (typeid(**$1) == typeid(AndChain)) {
            		$$ = $1;
            		if (typeid(**$3) == typeid(AndChain)) {
            			foreach (shared_ptr<Expression> element, dynamic_pointer_cast<AndChain>(*$3)->operands())
            				dynamic_pointer_cast<AndChain>(*$$)->insert_operand(element);
            		} else {
            			dynamic_pointer_cast<AndChain>(*$$)->insert_operand(*$3);
            		}
            	} else {
            		if (typeid(**$3) == typeid(AndChain)) {
            			$$ = new shared_ptr<Expression>(AndChain::create(*$1, dynamic_pointer_cast<AndChain>(*$3)->operands()[0]));
            			bool skipped = false;
            			foreach (shared_ptr<Expression> element, dynamic_pointer_cast<AndChain>(*$3)->operands())
            				if (skipped)
            					dynamic_pointer_cast<AndChain>(*$$)->insert_operand(element);
            				else
            					skipped = true;
            		} else {
            			$$ = new shared_ptr<Expression>(AndChain::create(*$1, *$3));
            		}
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "or" expression {
            	if (typeid(**$1) == typeid(OrChain)) {
            		$$ = $1;
            		if (typeid(**$3) == typeid(OrChain)) {
            			foreach (shared_ptr<Expression> element, dynamic_pointer_cast<OrChain>(*$3)->operands())
            				dynamic_pointer_cast<OrChain>(*$$)->insert_operand(element);
            		} else {
            			dynamic_pointer_cast<OrChain>(*$$)->insert_operand(*$3);
            		}
            	} else {
            		if (typeid(**$3) == typeid(OrChain)) {
            			$$ = new shared_ptr<Expression>(OrChain::create(*$1, dynamic_pointer_cast<OrChain>(*$3)->operands()[0]));
            			bool skipped = false;
            			foreach (shared_ptr<Expression> element, dynamic_pointer_cast<OrChain>(*$3)->operands())
            				if (skipped)
            					dynamic_pointer_cast<OrChain>(*$$)->insert_operand(element);
            				else
            					skipped = true;
            		} else {
            			$$ = new shared_ptr<Expression>(OrChain::create(*$1, *$3));
            		}
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }

            /*************** Comparison-chain expressions ***************/

          | expression '=' expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(EqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, EqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression '<' expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(LessThanOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, LessThanOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression '>' expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(GreaterThanOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, GreaterThanOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "<=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(LessEqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, LessEqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression ">=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(GreaterEqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, GreaterEqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "<>" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(UnequalOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, UnequalOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "<>=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(ComparableOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, ComparableOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotEqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotEqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!<" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotLessOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotLessOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!>" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotGreaterOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotGreaterOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!<=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotLessEqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotLessEqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!>=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotGreaterEqualOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotGreaterEqualOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!<>" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotUnequalOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotUnequalOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!<>=" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotComparableOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotComparableOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "==" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(IdentityOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, IdentityOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }
          | expression "!==" expression {
            	if (typeid(**$1) == typeid(ComparisonChain)) {
            		$$ = $1;
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_comparison_operator(NotIdentityOperator);
            		dynamic_pointer_cast<ComparisonChain>(*$$)->insert_operand(*$3);
            	} else {
            		$$ = new shared_ptr<Expression>(ComparisonChain::create(*$1, NotIdentityOperator, *$3));
            		delete $1;
            	}
            	(*$$)->set_location(@$);
            	delete $3;
            }

            /*************** Bracketed expression ***************/

          | '(' expression ')' { $$ = $2; }
          ;

subscripting: expression '[' expression ']' {
              	$$ = new shared_ptr<Subscripting>(Subscripting::create(*$1, *$3));
              	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
              }
            ;

assignment: expression "<-" expression {
            	$$ = new shared_ptr<Assignment>(Assignment::create(*$1, *$3));
            	(*$$)->set_location(@$);
            	delete $1;
            	delete $3;
            }
          ;

idassignment: expression "<--" expression {
              	$$ = new shared_ptr<IdAssignment>(IdAssignment::create(*$1, *$3));
              	(*$$)->set_location(@$);
              	delete $1;
              	delete $3;
              }
            ;

functioncall: expression '(' expressionlist ')' {
              	$$ = new shared_ptr<FunctionCall>(FunctionCall::create(*$1));
              	foreach (shared_ptr<Expression> expr, *$3)
              		(*$$)->insert_parameter(expr);
              	(*$$)->set_location(@$);
              	delete $1;
              	delete $3;
              }
            ;

range: expression ".." expression {
       		$$ = new shared_ptr<Range>(Range::create(*$1, *$3, IntegerLiteral::create(1)));
       		(*$$)->set_location(@$);
       		delete $1;
       		delete $3;
       }
     | expression ".." expression ".." expression {
       		$$ = new shared_ptr<Range>(Range::create(*$1, *$3, *$5));
       		(*$$)->set_location(@$);
       		delete $1;
       		delete $3;
       		delete $5;
       }
     ;

expressionlist: expressionlist ',' expression {
                	$1->push_back(*$3);
                	$$ = $1;
                	delete $3;
                }
              | expression {
                	$$ = new vector<shared_ptr<Expression> >;
                	$$->push_back(*$1);
                	delete $1;
                }
              | /* empty */ {
                	$$ = new vector<shared_ptr<Expression> >;
                }
              ;

ifstatement: "if" '(' expression ')' statement {
             	$$ = new shared_ptr<IfStatement>(IfStatement::create(*$3, *$5));
             	(*$$)->set_location(@$);
             	delete $3;
             	delete $5;
             }
           | "if" '(' expression ')' statement "else" statement {
             	$$ = new shared_ptr<IfStatement>(IfStatement::create(*$3, *$5, *$7));
             	(*$$)->set_location(@$);
             	delete $3;
             	delete $5;
             	delete $7;
             }
           ;

whilestatement: "while" '(' expression ')' statement {
                	$$ = new shared_ptr<WhileStatement>(WhileStatement::create(*$3, *$5));
                	(*$$)->set_location(@$);
                	delete $3;
                	delete $5;
                }
              ;

forstatement: "for" '(' identifier ',' range ')' statement {
              	$$ = new shared_ptr<ForStatement>(ForStatement::create(*$3, *$5, *$7));
              	(*$$)->set_location(@$);
              	delete $3;
              	delete $5;
              	delete $7;
              }
            ;

integerliteral: NUMBER {
                	$$ = new shared_ptr<IntegerLiteral>(IntegerLiteral::create(*$1));
                	(*$$)->set_location(@$);
                	delete $1;
                }
              ;

booleanliteral: BOOL_LITERAL {
                	$$ = new shared_ptr<BooleanLiteral>(BooleanLiteral::create($1));
                	(*$$)->set_location(@$);
                }
              ;

nullptr: "null" {
      	$$ = new shared_ptr<Null>(Null::create());
      	(*$$)->set_location(@$);
      }
    ;

reference: reference '.' IDENTIFIER {
           		$$ = $1;
           		(*$$)->insert_identifier(*$3);
           		(*$$)->set_location(@$);
           		delete $3;
           }
         |
           '.' IDENTIFIER {
           		$$ = new shared_ptr<Reference>(Reference::create(""));
           		(*$$)->insert_identifier(*$2);
           		(*$$)->set_location(@$);
           		delete $2;
           }
         |
           IDENTIFIER {
           		$$ = new shared_ptr<Reference>(Reference::create(*$1));
           		(*$$)->set_location(@$);
           		delete $1;
           }
         ;

identifier: IDENTIFIER {
            	$$ = new shared_ptr<Identifier>(Identifier::create(*$1));
            	(*$$)->set_location(@$);
            	delete $1; // FIXME: Memory corruption with all the new delete statements
            }
          ;
